/*
 * Copyright (C) 2010-2011 Graz University of Technology, Austria. All Rights reserved. 
 *
 * Contact: Simone Kopeinik <simone.kopeinik@tugraz.at>
 * 	   Graz University of Technology, Knowledge Management Institute, Brückenkopfgasse 1/6, 8020 Graz 	
 * 	   <http://www.kmi.tugraz.at/>
 * 
 * This software is part of the TARGET platform developed by the
 * TARGET EC-funded project www.reachyourtarget.org
 *
 * This software is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * The GNU General Public License is available at <http://www.gnu.org/licenses/>.
 *
 */
package at.tugraz.kmi.css.cbkst2.prereq;

import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

import org.apache.commons.collections15.Factory;

import at.tugraz.kmi.css.cbkst2.CbKSTVertex;
import at.tugraz.kmi.css.cbkst2.PrerequesiteRelation;
import edu.uci.ics.jung.graph.DirectedGraph;

/**
 * Constructs the transitive closure of the input graph. Copied from jgrapht.
 * 
 * @author Vinayak R. Borkar
 * @author Georg Öttl
 * @since May 5, 2007
 */
final class TransitiveClosureCalculator<V extends CbKSTVertex, E extends PrerequesiteRelation> {

	private final Factory<E>	provider;

	/**
	 * Private Constructor.
	 */
	TransitiveClosureCalculator(Factory<E> provider) {
		this.provider = provider;
	}

	// ~ Methods
	// ----------------------------------------------------------------

	/**
	 * Computes the transitive closure of the given graph.
	 * 
	 * @param graph
	 *            - Graph to compute transitive closure for.
	 */
	public void closeSimpleDirectedGraph(DirectedGraph<V, E> graph) {
		Collection<V> vertexSet = graph.getVertices();

		Set<V> newEdgeTargets = new HashSet<V>();

		// At every iteration of the outer loop, we add a path of length 1
		// between nodes that originally had a path of length 2. In the worst
		// case, we need to make floor(log |V|) + 1 iterations. We stop earlier
		// if there is no change to the output graph.

		int bound = computeBinaryLog(vertexSet.size());
		boolean done = false;
		for (int i = 0; !done && (i < bound); ++i) {
			done = true;
			for (V v1 : vertexSet) {
				newEdgeTargets.clear();

				Collection<E> outEdges = graph.getOutEdges(v1);
				if (outEdges != null) {
					for (E v1OutEdge : outEdges) {
						V v2 = graph.getDest(v1OutEdge);
						for (E v2OutEdge : graph.getOutEdges(v2)) {
							V v3 = graph.getDest(v2OutEdge);

							if (v1.equals(v3)) {
								// Its a simple graph, so no self loops.
								continue;
							}

							if (graph.findEdge(v1, v3) != null) {
								// There is already an edge from v1 ---> v3,
								// skip;
								continue;
							}

							newEdgeTargets.add(v3);
							done = false;
						}
					}
				}

				for (V v3 : newEdgeTargets) {
					graph.addEdge(this.provider.create(), v1, v3);
				}
			}
		}
	}

	/**
	 * Computes floor(log_2(n)) + 1
	 */
	private int computeBinaryLog(int n) {
		assert n >= 0;

		int result = 0;
		while (n > 0) {
			n >>= 1;
			++result;
		}

		return result;
	}
}

// End TransitiveClosure.java
